// https://www.lintcode.com/problem/validate-binary-search-tree/description
// 95. 验证二叉查找树
// 给定一个二叉树，判断它是否是合法的二叉查找树(BST)

// 一棵BST定义为：

// 节点的左子树中的值要严格小于该节点的值。
// 节点的右子树中的值要严格大于该节点的值。
// 左右子树也必须是二叉查找树。
// 一个节点的树也是二叉查找树。
// 样例
// 一个例子：

//   2
//  / \
// 1   4
//    / \
//   3   5
// 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.



/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

// 注意必须是左边所有节点的值都小于节点的值，不能仅仅判断左孩子...

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    
    // 个，遍历，再判断遍历记录
    // bool isValidBST(TreeNode * root) {
    //     if (!root)
    //     {
    //         return true;
    //     }
    //     vector<int> record;
    //     traverse(record, root);
    //     // vector<int> tmp = record;
    //     // sort(tmp.begin(), tmp.end());
    //     // return tmp == record;
    //     // 注意有相同节点的也算错
    //     int max = record[0];
    //     for (int i = 1; i < record.size(); ++i)
    //     {
    //         if (record[i] > max)
    //         {
    //             max = record[i];
    //         }
    //         else
    //         {
    //             return false;
    //         }
    //     }
    //     return true;
    // }
    
    // void traverse(vector<int>& record, TreeNode * root)
    // {
    //     if (!root)
    //     {
    //         return;
    //     }
    //     traverse(record, root->left);
    //     record.push_back(root->val);
    //     traverse(record, root->right);
    // }

    // 遍历直接判断，可以用last来记录，不需要vector   <递归记录遍历结果的方法>
    // TreeNode *last = NULL;
    // bool isValidBST(TreeNode * root) {
    //     if (!root)
    //     {
    //         return true;
    //     }
    //     if(!isValidBST(root->left))
    //     {
    //         return false;
    //     }
    //     if (last && last->val >= root->val)
    //     {
    //         return false;
    //     }
    //     last = root;
    //     isValidBST(root->right);
    // }
    
    
    // 分治法，记录min max，控制每个节点的范围   <递归记录节点范围的方法>
    bool divConq(TreeNode * root, long min, long max)
    {
        if (!root)
        {
            return true;        
        }
        if (min >= root->val || max <= root->val)
        {
            return false;
        }
        return divConq(root->left, min, root->val) && divConq(root->right, root->val, max);
    }
    bool isValidBST(TreeNode * root) {
        // return divConq(root, INT_MIN, INT_MAX);
        // {2147483647} true
        return divConq(root, LONG_MIN, LONG_MAX);
    }
};  